{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Super Washing Machines"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #array"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数组"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: findMinMoves"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #超级洗衣机"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>假设有 <code>n</code><strong>&nbsp;</strong>台超级洗衣机放在同一排上。开始的时候，每台洗衣机内可能有一定量的衣服，也可能是空的。</p>\n",
    "\n",
    "<p>在每一步操作中，你可以选择任意 <code>m</code> (<code>1 &lt;= m &lt;= n</code>) 台洗衣机，与此同时将每台洗衣机的一件衣服送到相邻的一台洗衣机。</p>\n",
    "\n",
    "<p>给定一个整数数组&nbsp;<code>machines</code> 代表从左至右每台洗衣机中的衣物数量，请给出能让所有洗衣机中剩下的衣物的数量相等的 <strong>最少的操作步数 </strong>。如果不能使每台洗衣机中衣物的数量相等，则返回 <code>-1</code> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>machines = [1,0,5]\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>\n",
    "第一步:    1     0 &lt;-- 5    =&gt;    1     1     4\n",
    "第二步:    1 &lt;-- 1 &lt;-- 4    =&gt;    2     1     3    \n",
    "第三步:    2     1 &lt;-- 3    =&gt;    2     2     2   \n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>machines = [0,3,0]\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>\n",
    "第一步:    0 &lt;-- 3     0    =&gt;    1     2     0    \n",
    "第二步:    1     2 --&gt; 0    =&gt;    1     1     1     \n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>machines = [0,2,0]\n",
    "<strong>输出：</strong>-1\n",
    "<strong>解释：</strong>\n",
    "不可能让所有三个洗衣机同时剩下相同数量的衣物。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == machines.length</code></li>\n",
    "\t<li><code>1 &lt;= n &lt;= 10<sup>4</sup></code></li>\n",
    "\t<li><code>0 &lt;= machines[i] &lt;= 10<sup>5</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [super-washing-machines](https://leetcode.cn/problems/super-washing-machines/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [super-washing-machines](https://leetcode.cn/problems/super-washing-machines/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,0,5]', '[0,3,0]', '[0,2,0]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution():\n",
    "\tdef findMinMoves(self, machines: List[int]) -> int:\n",
    "\t\ta,r=divmod(sum(machines),len(machines))\n",
    "\t\tif r!=0:\n",
    "\t\t\treturn -1\n",
    "\t\tres=cur=0\n",
    "\t\tfor c in machines:\n",
    "\t\t\tc+=cur\n",
    "\t\t\top=max(0-cur,0)+max(c-a,0)\n",
    "\t\t\tres=max(res,op)\n",
    "\t\t\tcur=c-a\n",
    "\t\treturn res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinMoves(self, machines: List[int]) -> int:\n",
    "        tot = sum(machines)\n",
    "        n = len(machines)\n",
    "        if tot % n:\n",
    "            return -1\n",
    "        avg = tot // n\n",
    "        ans, s = 0, 0\n",
    "        for num in machines:\n",
    "            num -= avg\n",
    "            s += num\n",
    "            ans = max(ans, abs(s), num)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinMoves(self, machines: List[int]) -> int:\n",
    "        tot = sum(machines)\n",
    "        n = len(machines)\n",
    "        if tot % n:\n",
    "            return -1\n",
    "        avg = tot // n\n",
    "        ans, s = 0, 0\n",
    "        for num in machines:\n",
    "            num -= avg\n",
    "            s += num\n",
    "            ans = max(ans, abs(s), num)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinMoves(self, machines: List[int]) -> int:\n",
    "        s = sum(machines)\n",
    "        n = len(machines)\n",
    "        if s%n!=0:\n",
    "            return -1\n",
    "  \n",
    "        ave = s//n\n",
    "        operation = [0]*n #由于传递可并行，取最大操作数的洗衣机\n",
    "        print(ave)\n",
    "        for i in range(n-1):\n",
    "            if machines[i]<ave:\n",
    "                deta = ave-machines[i]\n",
    "                machines[i] = ave\n",
    "                machines[i+1] -= deta\n",
    "                operation[i+1] += deta\n",
    "            elif machines[i]>ave:\n",
    "                deta = machines[i]-ave\n",
    "                machines[i] = ave\n",
    "                machines[i+1] += deta\n",
    "                operation[i] += deta\n",
    "\n",
    "        return max(operation)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinMoves(self, machines: List[int]) -> int:\n",
    "        s = sum(machines)\n",
    "        n = len(machines)\n",
    "        if s%n!=0:\n",
    "            return -1\n",
    "        res = 0\n",
    "        ave = s//n\n",
    "        operation = [0]*n #由于传递可并行，取最大操作数的洗衣机\n",
    "        print(ave)\n",
    "        for i in range(n):\n",
    "            if machines[i]<ave:\n",
    "                deta = ave-machines[i]\n",
    "                machines[i] = ave\n",
    "                machines[i+1] -= deta\n",
    "                operation[i+1] += deta\n",
    "            elif machines[i]>ave:\n",
    "                deta = machines[i]-ave\n",
    "                machines[i] = ave\n",
    "                machines[i+1] += deta\n",
    "                operation[i] += deta\n",
    "            res = max(res,operation[i])\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinMoves(self, machines: List[int]) -> int:\n",
    "        remain = 0\n",
    "        debt = 0\n",
    "        max_step = 0\n",
    "        n = len(machines)\n",
    "        avg = sum(machines) / n\n",
    "        if avg != int(avg):\n",
    "            return -1\n",
    "        for i in range(n):\n",
    "            if machines[i] == avg:\n",
    "                continue\n",
    "            elif machines[i] > avg:\n",
    "                remain += machines[i] - avg\n",
    "            elif machines[i] < avg:\n",
    "                debt -= avg - machines[i]\n",
    "            if abs(debt) > remain:\n",
    "                debt += remain\n",
    "                remain = 0\n",
    "            else:\n",
    "                remain -= abs(debt)\n",
    "                debt = 0\n",
    "            max_tmp = max(remain,abs(debt),machines[i]-avg)\n",
    "            if max_tmp > max_step:\n",
    "                max_step = max_tmp\n",
    "        return int(max_step)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinMoves(self, machines: List[int]) -> int:\n",
    "        sm, n = sum(machines), len(machines)\n",
    "        if sm%n == 0:\n",
    "            avg = sm//n\n",
    "            ans = 0\n",
    "            last = 0\n",
    "            for i in range(n):\n",
    "                if last<0 and machines[i]-avg>0:\n",
    "                    ans = max(ans, abs(machines[i]-avg-last))\n",
    "                else:\n",
    "                    ans = max(ans, abs(machines[i]-avg))\n",
    "                last = machines[i]-avg\n",
    "                if i!=n-1:\n",
    "                    machines[i+1] += machines[i] - avg\n",
    "                machines[i] = avg\n",
    "            return ans\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinMoves(self, machines: List[int]) -> int:\n",
    "        tot = sum(machines)\n",
    "        n = len(machines)\n",
    "        if tot % n:\n",
    "            return -1\n",
    "        avg = tot // n\n",
    "        ans, s = 0, 0\n",
    "        for num in machines:\n",
    "            num -= avg\n",
    "            s += num\n",
    "            ans = max(ans, abs(s), num)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinMoves(self, machines: List[int]) -> int:\n",
    "        v_sum, n = sum(machines), len(machines)\n",
    "        if v_sum % n != 0:\n",
    "            return -1\n",
    "        target = v_sum // n\n",
    "\n",
    "        ans = 0\n",
    "        pre_sum = 0\n",
    "        for i, v in enumerate(machines):\n",
    "            req = max(i * target - pre_sum, 0) + max((n - 1 - i) * target - (v_sum - pre_sum - v), 0)\n",
    "            ans = max(ans, req)\n",
    "            pre_sum += v\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinMoves(self, machines: List[int]) -> int:\n",
    "        if sum(machines) % len(machines) != 0:\n",
    "            return -1\n",
    "        n = len(machines)\n",
    "        target = sum(machines) // n\n",
    "        left_sum = 0\n",
    "        right_sum = 0\n",
    "        res = max(machines) - target\n",
    "        for i in range(1, n+1):\n",
    "            left_sum += machines[i-1]\n",
    "            right_sum += machines[n-i]\n",
    "            res = max(res, target*i - left_sum, target*i - right_sum)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinMoves(self, machines: List[int]) -> int:\n",
    "        if sum(machines) % len(machines) != 0:\n",
    "            return -1\n",
    "        n = len(machines)\n",
    "        target = sum(machines) // n\n",
    "        left_sum = 0\n",
    "        right_sum = 0\n",
    "        res = max(machines) - target\n",
    "        for i in range(1, n+1):\n",
    "            left_sum += machines[i-1]\n",
    "            right_sum += machines[n-i]\n",
    "            res = max(res, left_sum - target*i, right_sum - target*i)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution():\n",
    "\tdef findMinMoves(self, machines: List[int]) -> int:\n",
    "\t\ta,r=divmod(sum(machines),len(machines))\n",
    "\t\tif r!=0:\n",
    "\t\t\treturn -1\n",
    "\t\tres=cur=0\n",
    "\t\tfor c in machines:\n",
    "\t\t\tc+=cur\n",
    "\t\t\top=max(0-cur,0)+max(c-a,0)\n",
    "\t\t\tres=max(res,op)\n",
    "\t\t\tcur=c-a\n",
    "\t\treturn res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinMoves(self, machines: List[int]) -> int:\n",
    "        s = sum(machines)\n",
    "        n = len(machines)\n",
    "        if s%n!=0:\n",
    "            return -1\n",
    "  \n",
    "        ave = s//n\n",
    "        operation = [0]*n #由于传递可并行，取最大操作数的洗衣机\n",
    "        print(ave)\n",
    "        for i in range(n-1):\n",
    "            if machines[i]<ave:\n",
    "                deta = ave-machines[i]\n",
    "                machines[i] = ave\n",
    "                machines[i+1] -= deta\n",
    "                operation[i+1] += deta\n",
    "            elif machines[i]>ave:\n",
    "                deta = machines[i]-ave\n",
    "                machines[i] = ave\n",
    "                machines[i+1] += deta\n",
    "                operation[i] += deta\n",
    "            elif machines[i]==ave:\n",
    "                continue\n",
    "        return max(operation)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinMoves(self, machines: List[int]) -> int:\n",
    "        total = sum(machines)\n",
    "        m_len = len(machines)\n",
    "        avg = total//m_len\n",
    "        max_n = 0\n",
    "        num = 0\n",
    "        if total%m_len:\n",
    "            return -1\n",
    "        for m in machines:\n",
    "            s=m-avg\n",
    "            num+=s\n",
    "            max_n=max(max_n,abs(num),s)\n",
    "        return max_n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinMoves(self, machines: List[int]) -> int:\n",
    "        total = sum(machines)\n",
    "        n = len(machines)\n",
    "\n",
    "        if total % n != 0:\n",
    "            return -1\n",
    "\n",
    "        target = total // n\n",
    "        max_steps = 0\n",
    "        curr_sum = 0\n",
    "\n",
    "        for i in range(n):\n",
    "            diff = machines[i] - target\n",
    "            curr_sum += diff\n",
    "            max_steps = max(max_steps, abs(curr_sum), diff)\n",
    "\n",
    "        return max_steps"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinMoves(self, machines: List[int]) -> int:\n",
    "        total_sum = sum(machines)\n",
    "        n = len(machines)\n",
    "        if total_sum % n != 0:\n",
    "            return -1\n",
    "\n",
    "        avg = total_sum // n\n",
    "        res, cumsum = 0, 0\n",
    "\n",
    "        for num in machines:\n",
    "            num -= avg\n",
    "            cumsum += num\n",
    "            res = max(res, max(abs(cumsum), num))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinMoves(self, machines: List[int]) -> int:\n",
    "        tot = sum(machines)\n",
    "        n = len(machines)\n",
    "        if tot % n :\n",
    "            return -1\n",
    "        avg = tot // n\n",
    "        ans, s = 0, 0\n",
    "        for num in machines:\n",
    "            num -= avg\n",
    "            s += num\n",
    "            ans = max(ans,abs(s),num)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinMoves(self, machines: List[int]) -> int:\n",
    "        tot = sum(machines)\n",
    "        le = len(machines)\n",
    "        if tot % le != 0:\n",
    "            return -1\n",
    "        mean = tot // le\n",
    "        cur, ret = 0, 0\n",
    "        for m in machines:\n",
    "            m -= mean\n",
    "            cur += m\n",
    "            ret = max(ret, abs(cur), m)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinMoves(self, machines: List[int]) -> int:\n",
    "        num_clothes = sum(machines)\n",
    "        num_machines = len(machines)\n",
    "        if num_clothes % num_machines != 0:\n",
    "            return -1\n",
    "\n",
    "        avg_clothes = num_clothes // num_machines\n",
    "\n",
    "        ans, s = 0, 0\n",
    "        for clothes in machines:\n",
    "            clothes -= avg_clothes\n",
    "            s += clothes\n",
    "            ans = max(ans, abs(s), clothes)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''\n",
    "贪心\n",
    "'''\n",
    "class Solution:\n",
    "    def findMinMoves(self, machines: List[int]) -> int:\n",
    "        tot = sum(machines)\n",
    "        n = len(machines)\n",
    "        if tot % n:\n",
    "            return -1\n",
    "        avg = tot // n\n",
    "        ans, s = 0, 0\n",
    "        for num in machines:\n",
    "            num -= avg\n",
    "            s += num\n",
    "            ans = max(ans, abs(s), num)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinMoves(self, machines: List[int]) -> int:\n",
    "        s = sum(machines)\n",
    "        n = len(machines)\n",
    "        if s%n!=0:\n",
    "            return -1\n",
    "        res = 0\n",
    "        ave = s//n\n",
    "        operation = [0]*n #由于传递可并行，取最大操作数的洗衣机\n",
    "\n",
    "        for i in range(n):\n",
    "            if machines[i]<ave:\n",
    "                deta = ave-machines[i]\n",
    "                machines[i] = ave\n",
    "                machines[i+1] -= deta\n",
    "                operation[i+1] += deta\n",
    "            elif machines[i]>ave:\n",
    "                deta = machines[i]-ave\n",
    "                machines[i] = ave\n",
    "                machines[i+1] += deta\n",
    "                operation[i] += deta\n",
    "\n",
    "        return max(operation)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinMoves(self, machines: List[int]) -> int:\n",
    "        n = len(machines)\n",
    "        tot = sum(machines)\n",
    "        if tot % n != 0:\n",
    "            return -1\n",
    "        left = 0\n",
    "        right = tot\n",
    "        avg = tot // n\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            right -= machines[i]\n",
    "            if i > 0:\n",
    "                left += machines[i - 1]\n",
    "            l = max(avg * i - left, 0) # 0~i-1缺的衣服\n",
    "            r = max(avg * (n - i - 1) - right, 0) # i+1~n缺少的\n",
    "            res = max(res, l + r)\n",
    "        return res\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinMoves(self, arr: List[int]) -> int:\n",
    "        ss = 0\n",
    "        left_sum = 0\n",
    "        n = len(arr)\n",
    "        for i in range(n):\n",
    "            ss += arr[i]\n",
    "        if ss % n != 0:\n",
    "            return -1\n",
    "        avg = int(ss / n)\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            left_rest = left_sum - i * avg  # 为0和为n-1的情况也兼容了\n",
    "            right_rest = ss - left_sum - arr[i] - (n-i-1)*avg\n",
    "            if left_rest < 0 and right_rest < 0:\n",
    "                ans = max(ans, abs(left_rest) + abs(right_rest))\n",
    "            else:\n",
    "                ans = max(ans, max(abs(left_rest), abs(right_rest)))\n",
    "            left_sum += arr[i]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinMoves(self, machines: List[int]) -> int:\n",
    "\n",
    "        total, n = sum(machines), len(machines)\n",
    "        if total % n: \n",
    "            return -1\n",
    "\n",
    "        target, res, toRight = total // n, 0, 0\n",
    "        for m in machines:\n",
    "            toRight = m + toRight - target\n",
    "            # print(abs(toRight),res, m - target)\n",
    "            res = max(res, abs(toRight), m - target)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinMoves(self, machines: List[int]) -> int:\n",
    "        if sum(machines) % len(machines) != 0:\n",
    "            return -1\n",
    "        avg = sum(machines) // len(machines)\n",
    "        s = 0\n",
    "        ans = 0\n",
    "        for num in machines:\n",
    "            num -= avg\n",
    "            s += num\n",
    "            ans = max(ans, abs(s), num)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution():\n",
    "\tdef findMinMoves(self, machines: List[int]) -> int:\n",
    "\t\ta,r=divmod(sum(machines),len(machines))\n",
    "\t\tif r!=0:\n",
    "\t\t\treturn -1\n",
    "\t\tres=cur=0\n",
    "\t\tfor c in machines:\n",
    "\t\t\tc+=cur\n",
    "\t\t\top=max(0-cur,0)+max(c-a,0)\n",
    "\t\t\tres=max(res,op)\n",
    "\t\t\tcur=c-a\n",
    "\t\treturn res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinMoves(self, machines: List[int]) -> int:\n",
    "        tot = sum(machines)\n",
    "        n = len(machines)\n",
    "        if tot % n:\n",
    "            return -1\n",
    "        avg = tot // n\n",
    "        ans, s = 0, 0\n",
    "        for num in machines:\n",
    "            num -= avg\n",
    "            s += num\n",
    "            ans = max(ans, abs(s), num)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def findMinMoves(self, machines: List[int]) -> int:\n",
    "        n = len(machines)\n",
    "        sm = sum(machines)\n",
    "        a, r = divmod(sm, n)\n",
    "        if r: return -1\n",
    "        ans, s = 0, 0\n",
    "        for num in machines:\n",
    "            num -= a\n",
    "            s += num  # 前 i 项和 减去 a*i\n",
    "            ans = max(ans, abs(s), num)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinMoves(self, machines: List[int]) -> int:\n",
    "        s = len(machines)\n",
    "        sum_all = sum(machines)\n",
    "        if sum_all % s != 0:\n",
    "            return -1\n",
    "        avg = sum_all // s\n",
    "        sum_left = 0 # 左边的初始数据之和\n",
    "        res = 0\n",
    "        for i in range(s):\n",
    "            need_left = sum_left - i * avg\n",
    "            need_right = (sum_all - sum_left - machines[i]) - (s-i-1) * avg\n",
    "            if need_left<0 and need_right<0:\n",
    "                res = max(res, abs(need_left) + abs(need_right))\n",
    "            else:\n",
    "                res = max(res, max(abs(need_left), abs(need_right)))\n",
    "            sum_left += machines[i]\n",
    "        return res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinMoves(self, machines: List[int]) -> int:\n",
    "        n = len(machines)\n",
    "        sum = 0\n",
    "        for m in machines:\n",
    "            sum += m\n",
    "        if sum % n:\n",
    "            return -1\n",
    "        avg = sum // n\n",
    "        ans = 0\n",
    "        delta = 0\n",
    "        for m in machines:\n",
    "            delta += m - avg\n",
    "            ans = max(ans, abs(delta), m-avg)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinMoves(self, m: List[int]) -> int:\n",
    "        n = len(m)\n",
    "        if (sum(m))%n:\n",
    "            return -1\n",
    "        a = sum(m)//n\n",
    "        b = [j-a for j in m]\n",
    "        pre = 0\n",
    "        ans = 0\n",
    "        for j in b:\n",
    "            tmp = j+pre \n",
    "            ans = max([abs(tmp), ans, j])\n",
    "            pre = tmp\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinMoves(self, machines: List[int]) -> int:\n",
    "        n, s = len(machines), sum(machines)\n",
    "        if s % n != 0:\n",
    "            return -1\n",
    "        m = s // n\n",
    "        machines = [num - m for num in machines]\n",
    "        # 大于0表示需要往外移动而小于0表示需要往内移进\n",
    "        ans = pre = 0\n",
    "        for num in machines:\n",
    "            # abs(pre)表示machines[:i+1]与machines[i+1:]之间需要移动衣服的情况\n",
    "            pre += num\n",
    "            # num表示machines[i]往左右移动衣服的情况\n",
    "            ans = max(abs(pre), num, ans)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinMoves(self, machines: List[int]) -> int:\n",
    "        if sum(machines)%len(machines)!=0:\n",
    "            return -1\n",
    "        k = sum(machines)//len(machines)\n",
    "        cur = 0\n",
    "        ans= 0\n",
    "        for x in machines:\n",
    "            #if cur*(cur+x-k)>0:\n",
    "            #    cur+=x-k\n",
    "            #else:\n",
    "            #    cur=x-k\n",
    "            cur+=x-k\n",
    "            ans=max(abs(cur),ans,x-k)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinMoves(self, machines: List[int]) -> int:\n",
    "        tot = sum(machines)\n",
    "        n = len(machines)\n",
    "        if tot % n:\n",
    "            return -1\n",
    "        avg = tot // n\n",
    "        ans, s = 0, 0\n",
    "        for num in machines:\n",
    "            num -= avg\n",
    "            s += num\n",
    "            ans = max(ans, abs(s), num)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinMoves(self, machines: List[int]) -> int:\n",
    "        tot = sum(machines)\n",
    "        n = len(machines)\n",
    "        if tot % n:\n",
    "            return -1\n",
    "        avg = tot // n\n",
    "        ans, s = 0, 0\n",
    "        for num in machines:\n",
    "            num -= avg\n",
    "            s += num\n",
    "            ans = max(ans, abs(s), num)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution():\n",
    "\tdef findMinMoves(self, machines: List[int]) -> int:\n",
    "\t\ta,r=divmod(sum(machines),len(machines))\n",
    "\t\tif r!=0:\n",
    "\t\t\treturn -1\n",
    "\t\tres=cur=0\n",
    "\t\tfor c in machines:\n",
    "\t\t\tc+=cur\n",
    "\t\t\top=max(0-cur,0)+max(c-a,0)\n",
    "\t\t\tres=max(res,op)\n",
    "\t\t\tcur=c-a\n",
    "\t\treturn res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinMoves(self, machines: List[int]) -> int:\n",
    "        '''\n",
    "        传功大法：\n",
    "        1.当前不够向下一个借，借到自己够（不管下一个够不够，借就完事）；\n",
    "        2.当前有余就传给下一个，传到自己刚好够（不管下一个是多是少，传就完事）。\n",
    "\n",
    "        这样的策略保证每台洗衣机左侧一定全是数量刚好够的机器，借或者传的方向只能向右。\n",
    "        每个位置的传功数分为 别人向自己借的、自己主动传给别人的 两个部分，\n",
    "        由于不同洗衣机把衣服传给别的机子的传功操作是并行的，因此结果只要取各个机子传功数的最大值即可。\n",
    "\n",
    "        为什么这样的解法会是最优的呢？\n",
    "\n",
    "        解释：\n",
    "        要想操作数最小，羊毛总要逮着近的薅。\n",
    "\n",
    "        从第1台洗衣机开始分析，如果第1台洗衣机里衣服少了，只能往右边去借；\n",
    "        同理，如果多了，也只能丢给右边的洗衣机，保证自己的数量刚刚好。\n",
    "\n",
    "        那现在来看第2台洗衣机，假如第2台洗衣机的衣服少了，应该向谁借呢？\n",
    "\n",
    "        假如现在向前面衣服数量刚刚好的第1台洗衣机去借，\n",
    "        势必会引起第1台洗衣机向其他洗衣机再去借，徒增一轮操作，这样肯定是不合算的。\n",
    "        因此第2台洗衣机只能再向后面的洗衣机去借。\n",
    "\n",
    "        若第2台洗衣机衣服多了，思考传衣服的方向也是用的同样的分析方法。\n",
    "\n",
    "        由此可见，这样的操作得到的操作次数是最优的。\n",
    "        '''\n",
    "        n,summ = len(machines),sum(machines)\n",
    "        if summ%n: return -1\n",
    "\n",
    "        target = summ//n\n",
    "        operation = [0]*n\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            if machines[i] < target:\n",
    "                borrow = target-machines[i]\n",
    "                machines[i] = target\n",
    "                machines[i+1] -= borrow\n",
    "                operation[i+1] += borrow\n",
    "            elif machines[i] > target:\n",
    "                lend = machines[i]-target\n",
    "                machines[i] = target\n",
    "                machines[i+1] += lend\n",
    "                operation[i] += lend\n",
    "            res = max(res,operation[i])\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinMoves(self, machines: List[int]) -> int:\n",
    "    \n",
    "        tot = sum(machines)\n",
    "        n = len(machines)\n",
    "        if tot % n:\n",
    "            return -1\n",
    "        avg = tot // n\n",
    "        ans = s = 0\n",
    "        for x in machines:\n",
    "            x -= avg\n",
    "            s += x\n",
    "            ans = max(ans, x, abs(s))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinMoves(self, machines: List[int]) -> int:\n",
    "        if len(machines)==1:return 0\n",
    "        if sum(machines)%len(machines)!=0:return -1\n",
    "        avg = sum(machines) // len(machines)\n",
    "        res = 0\n",
    "\n",
    "        for i in range(len(machines)):\n",
    "            left = sum(machines[:i])-len(machines[:i])*avg\n",
    "            right = sum(machines[i+1:])-len(machines[i+1:])*avg\n",
    "            ziji = machines[i]-avg\n",
    "    \n",
    "            tem = [i for i in (left,right,ziji)]\n",
    "            res = max(res,max(tem))\n",
    "            \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution():\n",
    "\tdef findMinMoves(self, machines: List[int]) -> int:\n",
    "\t\ta,r=divmod(sum(machines),len(machines))\n",
    "\t\tif r!=0:\n",
    "\t\t\treturn -1\n",
    "\t\tres=cur=0\n",
    "\t\tfor c in machines:\n",
    "\t\t\tc+=cur\n",
    "\t\t\top=max(0-cur,0)+max(c-a,0)\n",
    "\t\t\tres=max(res,op)\n",
    "\t\t\tcur=c-a\n",
    "\t\treturn res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinMoves(self, machines: List[int]) -> int:\n",
    "        s = len(machines)\n",
    "        sum_all = sum(machines)\n",
    "        if sum_all % s != 0:\n",
    "            return -1\n",
    "        avg = sum_all / s\n",
    "        sum_left = 0 # 左边的初始数据之和\n",
    "        res = 0\n",
    "        for i in range(s):\n",
    "            need_left = sum_left - i * avg\n",
    "            need_right = (sum_all - sum_left - machines[i]) - (s-i-1) * avg\n",
    "            if need_left<0 and need_right<0:\n",
    "                res = max(res, abs(need_left) + abs(need_right))\n",
    "            else:\n",
    "                res = max(res, max(abs(need_left), abs(need_right)))\n",
    "            sum_left += machines[i]\n",
    "        return int(res)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinMoves(self, machines: List[int]) -> int:\n",
    "        '''\n",
    "        传功大法：\n",
    "        1.当前不够向下一个借，借到自己够（不管下一个够不够，借就完事）；\n",
    "        2.当前有余就传给下一个，传到自己刚好够（不管下一个是多是少，传就完事）。\n",
    "\n",
    "        这样的策略保证每台洗衣机左侧一定全是数量刚好够的机器，借或者传的方向只能向右。\n",
    "        每个位置的传功数分为 别人向自己借的、自己主动传给别人的 两个部分，\n",
    "        由于不同洗衣机把衣服传给别的机子的传功操作是并行的，因此结果只要取各个机子传功数的最大值即可。\n",
    "\n",
    "        为什么这样的解法会是最优的呢？\n",
    "\n",
    "        解释：\n",
    "        要想操作数最小，羊毛总要逮着近的薅。\n",
    "\n",
    "        从第1台洗衣机开始分析，如果第1台洗衣机里衣服少了，只能往右边去借；\n",
    "        同理，如果多了，也只能丢给右边的洗衣机，保证自己的数量刚刚好。\n",
    "\n",
    "        那现在来看第2台洗衣机，假如第2台洗衣机的衣服少了，应该向谁借呢？\n",
    "\n",
    "        假如现在向前面衣服数量刚刚好的第1台洗衣机去借，\n",
    "        势必会引起第1台洗衣机向其他洗衣机再去借，徒增一轮操作，这样肯定是不合算的。\n",
    "        因此第2台洗衣机只能再向后面的洗衣机去借。\n",
    "\n",
    "        若第2台洗衣机衣服多了，思考传衣服的方向也是用的同样的分析方法。\n",
    "\n",
    "        由此可见，这样的操作得到的操作次数是最优的。\n",
    "        '''\n",
    "        tot = sum(machines)\n",
    "        n = len(machines)\n",
    "        if tot % n:\n",
    "            return -1\n",
    "        avg = tot // n\n",
    "        ans, s = 0, 0\n",
    "        for num in machines:\n",
    "            num -= avg\n",
    "            s += num\n",
    "            ans = max(ans, abs(s), num)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinMoves(self, machines: List[int]) -> int:\n",
    "        N = len(machines)\n",
    "        total = sum(machines)\n",
    "        if total % N != 0:\n",
    "            return -1\n",
    "        avg = total // N\n",
    "        leftSum = 0\n",
    "        res = 0\n",
    "        for i in range(N):\n",
    "            leftRest = leftSum - (i * avg)\n",
    "            rightRest = total - leftSum - machines[i] - (N - 1 - i) * avg\n",
    "            if leftRest < 0 and rightRest < 0:\n",
    "                res = max(res, abs(leftRest) + abs(rightRest))\n",
    "            else:\n",
    "                res = max(res, max(abs(leftRest), abs(rightRest)))\n",
    "            leftSum += machines[i]\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinMoves(self, machines: List[int]) -> int:\n",
    "        n = len(machines)\n",
    "        s = sum(machines)\n",
    "        if s % n != 0:\n",
    "            return -1\n",
    "        avg = s // n\n",
    "        s = 0\n",
    "        ans = 0\n",
    "        for x in machines:\n",
    "            x -= avg\n",
    "            s += x\n",
    "            ans = max(ans, abs(s), x)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinMoves(self, machines: List[int]) -> int:\n",
    "        n = len(machines)\n",
    "        tot_sum = sum(machines)\n",
    "        if tot_sum % n != 0:        \n",
    "            return -1\n",
    "        \n",
    "        aver_ = tot_sum // n        #每台机器，最终的衣服数\n",
    "\n",
    "        for i in range(n):\n",
    "            machines[i] -= aver_    #现有的-最终的=中间变动的件数（+/-）\n",
    "        \n",
    "        res = 0\n",
    "        \n",
    "        #----单台单台地看\n",
    "        for i in range(n):\n",
    "            res = max(res, machines[i])\n",
    "\n",
    "        #----隔板的思想（全局一块隔板，尝试每个位置）。\n",
    "        presum_diff = 0\n",
    "        for i in range(n):\n",
    "            presum_diff += machines[i]      #左侧（含i）累积了多少“不平衡”\n",
    "            flow_passby = abs(presum_diff)  #经过第i台机器的流量\n",
    "            res = max(res, flow_passby)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinMoves(self, machines) -> int:\n",
    "        n = len(machines)\n",
    "        sumc = sum(machines)\n",
    "\n",
    "        if sumc % n != 0:\n",
    "            return -1\n",
    "\n",
    "        avg = sumc // n\n",
    "        count, m = 0, 0\n",
    "\n",
    "        for i in machines:\n",
    "            m += i - avg\n",
    "            count = max(count, abs(m), i - avg)\n",
    "\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinMoves(self, m: List[int]) -> int:\n",
    "        tot = sum(m)\n",
    "        n = len(m)\n",
    "        if tot % n != 0:\n",
    "            return -1\n",
    "        avg = tot // n\n",
    "        ans = s = 0\n",
    "        for v in m:\n",
    "            v -= avg\n",
    "            s += v\n",
    "            # 必须是v，而不能是abs(v)是因为v负数时说明需要其他方向的机器过来\n",
    "            # 而可以同时有多个机器的衣服过来，但只会出去一个\n",
    "            ans = max(ans, abs(s), v)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinMoves(self, machines: List[int]) -> int:\n",
    "        tot = sum(machines)\n",
    "        n = len(machines)\n",
    "        if tot % n:\n",
    "            return -1\n",
    "        avg = tot // n\n",
    "        ans, s = 0, 0\n",
    "        for num in machines:\n",
    "            num -= avg\n",
    "            s += num\n",
    "            ans = max(ans, abs(s), num)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinMoves(self, machines: List[int]) -> int:\n",
    "        if len(machines)==1:return 0\n",
    "        if sum(machines)%len(machines)!=0:return -1\n",
    "        avg = sum(machines) // len(machines)\n",
    "        res = 0\n",
    "\n",
    "        for i in range(len(machines)):\n",
    "            left = sum(machines[:i]) - len(machines[:i]) * avg\n",
    "            right = sum(machines[i + 1:]) - len(machines[i + 1:]) * avg\n",
    "            if left<0 and right<0:\n",
    "                res = max(res,abs(left+right))\n",
    "            elif left > 0 and right > 0:\n",
    "                res = max(res,max(left,right))\n",
    "            else:\n",
    "                res = max(res,max(abs(left),abs(right)))\n",
    "                \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinMoves(self, machines: List[int]) -> int:\n",
    "        n = len(machines)\n",
    "        total = sum(machines)\n",
    "        if not total%n == 0:\n",
    "            return -1\n",
    "        avg = total//n\n",
    "\n",
    "        diff = [machines[i]-avg for i in range(n)]\n",
    "        max_diff = -float('inf')\n",
    "        pre = 0\n",
    "        max_pre = -float('inf')\n",
    "        for i in range(n):\n",
    "            max_diff = max(max_diff,diff[i])\n",
    "            pre += diff[i]\n",
    "            max_pre = max(max_pre, abs(pre))\n",
    "        return max(max_pre, max_diff)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinMoves(self, machines: List[int]) -> int:\n",
    "        '''\n",
    "        原则是：有余就全给下一个的，有少的就向下一个要够\n",
    "        '''\n",
    "        n = len(machines)\n",
    "        sums = sum(machines)\n",
    "        if sums % n != 0:\n",
    "            return -1\n",
    "        target = sums // n\n",
    "        operations = [0] * n\n",
    "        for idx in range(n-1):\n",
    "            if machines[idx] < target:          # 当前不够向下一个借\n",
    "                borrow = target-machines[idx]\n",
    "                machines[idx] += borrow\n",
    "                machines[idx+1] -= borrow\n",
    "                operations[idx+1] += borrow     # 下一个借出\n",
    "            elif machines[idx] > target:\n",
    "                lend = machines[idx] - target\n",
    "                machines[idx] -= lend\n",
    "                machines[idx+1] += lend\n",
    "                operations[idx] += lend         # 当前借出 \n",
    "        return max(operations)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinMoves(self, machines: List[int]) -> int:\n",
    "        if sum(machines) % len(machines) != 0:\n",
    "            return -1\n",
    "        \n",
    "        n = len(machines)\n",
    "        avg = sum(machines) / n\n",
    "        \n",
    "        left, right = 0,0\n",
    "        a = [0] * len(machines)\n",
    "        \n",
    "        \n",
    "       \n",
    "\n",
    "\n",
    "        for i in range(n):\n",
    "            left = sum(machines[0:i]) - avg * i\n",
    "            right = sum(machines[i + 1 :]) - avg * (n - i - 1)\n",
    "            print(left, right)\n",
    "            if left < 0 and right < 0:\n",
    "                a[i] = abs(left) + abs(right)\n",
    "            else:\n",
    "                a[i] = max(abs(left), abs(right))\n",
    "        return int(max(a))\n",
    "            \n",
    "\n",
    "         "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinMoves(self, machines: List[int]) -> int:\n",
    "        n = len(machines)\n",
    "        s = sum(machines)\n",
    "        if s % n:\n",
    "            return -1\n",
    "        for i in range(n):\n",
    "            machines[i] -= s // n\n",
    "        s = 0\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            s += machines[i]\n",
    "            ans = max(machines[i],abs(s),ans)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinMoves(self, machines: List[int]) -> int:\n",
    "        dresses = sum(machines)\n",
    "        n = len(machines)\n",
    "        if dresses % n != 0:\n",
    "            return -1\n",
    "        \n",
    "        num = dresses // n\n",
    "        moves = [0] * n\n",
    "        \n",
    "        for i in range(n):\n",
    "            if machines[i] < num:\n",
    "                moves[i+1] += num - machines[i]\n",
    "                machines[i+1] -= num - machines[i]\n",
    "            elif machines[i] > num:\n",
    "                moves[i] += machines[i] - num\n",
    "                machines[i+1] += machines[i] - num\n",
    "        \n",
    "        return max(moves)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinMoves(self, machines: List[int]) -> int:\n",
    "\n",
    "        n = len(machines)\n",
    "        s = sum(machines)\n",
    "        if s % n != 0:  return -1\n",
    "        m = s // n\n",
    "        a = t = 0\n",
    "        for num in machines:\n",
    "            dif = num - m\n",
    "            t += num - m\n",
    "            a = max(a, dif, abs(t))\n",
    "        return a\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinMoves(self, machines: List[int]) -> int:\n",
    "        if sum(machines) % len(machines) != 0:\n",
    "            return -1\n",
    "        \n",
    "        average = sum(machines) // len(machines)\n",
    "        answer = 0\n",
    "        sum_a = 0\n",
    "        sum_m = 0\n",
    "        for machine in machines:\n",
    "            sum_a += average\n",
    "            sum_m += machine\n",
    "            if abs(sum_a - sum_m) > answer:\n",
    "                answer = abs(sum_a - sum_m)\n",
    "            if machine - average > answer:\n",
    "                answer = machine - average\n",
    "            if (average - machine + 1) // 2 > answer:\n",
    "                answer = (average - machine + 1) // 2\n",
    "        return answer\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def findMinMoves(self, machines: List[int]) -> int:\r\n",
    "        S=sum(machines)\r\n",
    "        if S%len(machines):\r\n",
    "            return -1\r\n",
    "        avg=S//len(machines)\r\n",
    "        ans,s=0,0\r\n",
    "        for m in machines:\r\n",
    "            m-=avg\r\n",
    "            s+=m\r\n",
    "            ans=max(ans,abs(s),m)\r\n",
    "        return ans\r\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinMoves(self, machines: List[int]) -> int:\n",
    "        n = len(machines)\n",
    "        al = sum(machines)\n",
    "\n",
    "        if al % n != 0:\n",
    "            return -1\n",
    "\n",
    "        avg = al // n\n",
    "\n",
    "        dp = [0] * n\n",
    "\n",
    "        mx = -1\n",
    "        for i in range(n):\n",
    "            dp[i] = machines[i] - avg\n",
    "            # mx = max(mx, abs(dp[i]))\n",
    "        print(dp)\n",
    "        \n",
    "        s = 0\n",
    "        for i in range(n):\n",
    "            s += dp[i]\n",
    "            mx = max(mx, dp[i], abs(s))\n",
    "            # dp[i+1] += dp[i]\n",
    "        return mx"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinMoves(self, machines: List[int]) -> int:\n",
    "        n = len(machines)\n",
    "        sumn = 0\n",
    "        for i in range(n):\n",
    "            sumn += machines[i]\n",
    "        if sumn % n != 0:\n",
    "            return -1\n",
    "        target = sumn // n\n",
    "        op = [0 for _ in range(n)]\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            if machines[i] < target:\n",
    "                diff = target - machines[i]\n",
    "                machines[i+1] -= diff\n",
    "                op[i+1] += diff\n",
    "            if machines[i] > target:\n",
    "                diff = machines[i] - target\n",
    "                machines[i+1] += diff\n",
    "                op[i] += diff\n",
    "            ans = max(ans, op[i])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinMoves(self, machines: List[int]) -> int:\n",
    "        total_num = 0\n",
    "        for i in machines:\n",
    "            total_num += i\n",
    "        if total_num/len(machines) % 1 != 0:\n",
    "            return -1\n",
    "        else:\n",
    "            distence = []\n",
    "            for i in machines:\n",
    "                distence.append(i - total_num/len(machines))\n",
    "            maxabs = 0\n",
    "            for i in distence:\n",
    "                if maxabs < abs(i):\n",
    "                    maxabs = i\n",
    "            for i in range(len(distence)-1):\n",
    "                distence[i+1] += distence[i]\n",
    "                if maxabs < abs(distence[i+1]):\n",
    "                    maxabs = abs(distence[i+1])\n",
    "\n",
    "            return int(maxabs)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinMoves(self, machines: List[int]) -> int:\n",
    "        n = len(machines)\n",
    "        total = sum(machines)\n",
    "        if total % n:\n",
    "            return -1\n",
    "        target = total // n\n",
    "        operation = [0 for _ in range(n)]\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            if machines[i] < target:\n",
    "                 #不够，向后借\n",
    "                borrow = target - machines[i]\n",
    "                machines[i + 1] -= borrow \n",
    "                operation[i + 1] += borrow\n",
    "               \n",
    "            elif machines[i] > target:\n",
    "                lend = machines[i] - target\n",
    "                machines[i + 1] += lend\n",
    "                operation[i] += lend\n",
    "            \n",
    "\n",
    "                \n",
    "        \n",
    "        return max(operation)\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinMoves(self, machines):\n",
    "        total_sum = sum(machines)\n",
    "        N = len(machines)\n",
    "\n",
    "        left_sum = [0] * N\n",
    "        right_sum = [0] * N\n",
    "\n",
    "        total_sum = machines[0]\n",
    "\n",
    "        for i in range(1, N):\n",
    "            total_sum += machines[i]\n",
    "            left_sum[i] = left_sum[i - 1] + machines[i - 1]\n",
    "\n",
    "        for i in range(N - 2, -1, -1):\n",
    "            right_sum[i] = right_sum[i + 1] + machines[i + 1]\n",
    "\n",
    "        avg = total_sum // N\n",
    "\n",
    "        if total_sum % N != 0:\n",
    "            return -1\n",
    "\n",
    "        turns = 0\n",
    "\n",
    "        for i in range(N):\n",
    "            left_machines = i\n",
    "            right_machines = N - i - 1\n",
    "            left_clothes = left_sum[i] - left_machines * avg\n",
    "            right_clothes = right_sum[i] - right_machines * avg\n",
    "\n",
    "            if left_clothes < 0 and right_clothes < 0:\n",
    "                turns = max(turns, abs(left_clothes + right_clothes))\n",
    "            else:\n",
    "                turns = max(turns, max(abs(left_clothes), abs(right_clothes)))\n",
    "\n",
    "        return turns\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
